
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1735. -- [Usaco2005 jan]Muddy Fields -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1735: [Usaco2005 jan]Muddy Fields</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>63&nbsp;&nbsp;<span class=green>Solved: </span>44<br>[<a href='submitpage.php?id=1735'>Submit</a>][<a href='problemstatus.php?id=1735'>Status</a>][<a href='bbs.php?id=1735'>Discuss</a>]</center><h2>Description</h2><div class=content>Rain has pummeled the cows' field, a rectangular grid of R rows and
C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass,
the rain makes some patches of bare earth quite muddy. The
cows, being meticulous grazers, don't want to get their hooves dirty
while they eat.

To prevent those muddy hooves, Farmer John will place a number of
wooden boards over the muddy parts of the cows' field.  Each of the
boards is 1 unit wide, and can be any length long.  Each board must
be aligned parallel to one of the sides of the field.

Farmer John wishes to minimize the number of boards needed to cover
the muddy spots, some of which might require more than one board
to cover.  The boards may not cover any grass and deprive the cows
of grazing area but they can overlap each other.

Compute the minimum number of boards FJ requires to cover all the mud in
the field.

</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Each line contains a string of C characters, with '*'
        representing a muddy patch, and '.' representing a grassy
        patch. No spaces are present.

</div><h2>Output</h2><div class=content>* Line 1: A single integer representing the number of boards FJ needs.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 4<br />
*.*.<br />
.***<br />
***.<br />
..*.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>4<br />
<br />
OUTPUT DETAILS:<br />
<br />
Boards 1, 2, 3 and 4 are placed as follows:<br />
1.2.<br />
.333<br />
444.<br />
..2.<br />
Board 2 overlaps boards 3 and 4.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1735'>Submit</a>][<a href='problemstatus.php?id=1735'>Status</a>][<a href='bbs.php?id=1735'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
